package toOffer;

import java.time.Instant;
import java.util.*;
import java.util.stream.Collectors;

/**
 * <h3>toOffer</h3>
 *
 * @author YuanAo
 * @date 2024/5/21 11:39
 * @description <p>加一</p>
 */


public class No66 {
    public static void main(String[] args) {
        int[] digits = {1, 2, 9};
        int[] ints = plusOne(digits);
        for (int i : ints) {
            System.out.print(i + " ");
        }
    }


    /**
     * 思路：
     * 垃圾方法，从数组里面的第二个数开始判断前一个数是否等于 10，等于就把前一个数变 0、当前数 +1。如果当前数是数组里的最后一个数的话需要重新加一个数
     *
     * @param digits
     * @return
     */
    public static int[] plusOne1(int[] digits) {
        if (digits.length == 1 && digits[0] == 9) {
            return new int[]{1, 0};
        }
        List<Integer> newList = Arrays.stream(digits).boxed().collect(Collectors.toList());
        Collections.reverse(newList);
        newList.set(0, newList.get(0) + 1);
        for (int i = 1; i < newList.size(); i++) {
            if (newList.get(i - 1) == 10) {
                newList.set(i - 1, 0);
                newList.set(i, newList.get(i) + 1);
            }
            if (newList.get(newList.size() - 1) == 10) {
                newList.set(newList.size() - 1, 0);
                newList.add(1);
            }
        }
        Collections.reverse(newList);
        return newList.stream().mapToInt(o -> o).toArray();
    }

    /**
     * 跟上面的思路是一样的，就是少了把静态数组转动态、再反转的过程。所以这个时间复杂度要快一点
     * @param digits
     * @return
     */
    public static int[] plusOne(int[] digits) {
        if (digits.length == 1 && digits[0] == 9) {
            return new int[]{1, 0};
        }
        digits[digits.length - 1] += 1;

        for (int i = digits.length - 2; i >= 0; i--) {
            if (digits[i + 1] == 10) {
                digits[i + 1] = 0;
                digits[i] +=  1;
            }
            if (i == 0 && digits[i] == 10){
                digits[i] = 0;
                int[] newInts = new int[digits.length + 1];
                newInts[0] = 1;
                for (int j = 1; j < newInts.length; j++) {
                    newInts[j] = digits[j-1];
                }
                return newInts;
            }
        }

        return digits;
    }
}
